IA. Field of the Invention
The present invention is related to solving complex problems. Specifically, the present invention is related to a method of solving a test generation problem for sequential circuits. The present invention is embodied in methods for solving a problem; methods for solving a test generation problem for sequential circuits; a method for generating test vectors for testing sequential circuits; systems for generating test vectors; and a computer program product including a computer code for solving a test generation problem for sequential circuits.
IB. Background of the Invention
Complex problems are often defined by a large set of constraints. Test generation for testing a sequential circuit is an example of such a complex problem. For some problems, the only practical method of obtaining a solution may be an on-line method. FIG. 20 shows a flowchart describing an on-line method. According to these on-line methods, a subset of constraints that correspond to a sub-problem of the main problem are first considered as shown in 20.1 and 20.2. A solution is derived for this sub-problem 20.3. Because such a solution for the sub-problem satisfies only a subset of constraints of the main problem, it is referred to as the partial solution. If no partial solution exists for the sub-problem, then it is clear that the main problem itself has no solution. In such a case a subset of constraints that prevent the existence of a solution is identified 20.4.
A check is made to see if a partial solution additionally satisfies all constraints of the main problem 20.5. In such a case, the partial solution itself is a complete solution to the main problem 20.6. Otherwise, if the partial solution does not satisfy additional constraints that are not part of the constraints corresponding to the sub-problem, an on line method augments the subset of constraints for the sub-problem. This is done by including one or more of the additional constraints 20.7. After augmentation, the on-line method derives another partial solution. This process is repeated, as shown in the loop of FIG. 20, until either a partial solution that satisfies all constraints is derived or a subset of constraints is identified that does not have a partial solution. Usually, either a solution is found or it is established that no solution is possible well before the final iteration that will have to consider all constraints.
An example of an on-line method is the conventional time-frame expansion method. Consider solving the sequential test generation problem using the conventional time-frame expansion method. The time frame expansion method is described in detail in the following references: G. R. Puzzle and J. P. Both, xe2x80x9cA Heuristic Algorithm for the Testing of Asynchronous Circuits,xe2x80x9d IEEE Trans. on Computers, pp. 639-647, June 1971; R. Marlene, xe2x80x9cAn Efficient Test Generation System for Sequential Circuits,xe2x80x9d 23Rd. Design Automation Conference, June 1986, pp. 250-256; H-K. T. Ma, et. Al., xe2x80x9cTest Generation for Sequential Circuits,xe2x80x9d IEEE Trans. on Computer-Aided Design, Vol. 7, No. 10, pp. 1081-1093, October 1988; M. Scull and E. Auto, xe2x80x9cESSENTIAL: An Efficient Self-Learning Test Pattern Generation Algorithm For Sequential Circuits,xe2x80x9d 1989 International Test Conference, pp. 28-37; W. Chewing and T. Chakraborty, xe2x80x9cGentestxe2x80x94An Automatic Test Generation System for Sequential Circuits,xe2x80x9d IEEE Computer pp. 43-49, April 1989, D. H. Lee and S. M. Reddy, xe2x80x9cA New Test Generation Method for Sequential circuits,xe2x80x9d Proc. of International Conference on Computer Aided Design, pp. 446-449, 1991; T. Niermann and J. Patel, xe2x80x9cHITEC: A Test Generation Package for Sequential Circuits,xe2x80x9d European Conf. On Design Automation 1991, pp. 214-218 and T. Kelsey, K. Saluja, and S. Lee, xe2x80x9cAn Efficient Algorithm for Sequential Circuit Test Generation,xe2x80x9d IEEE Trans. on Computer, vol. 42, pp. 1361-1371, November 1993.
In the time-frame expansion method, a test generation problem for sequential circuits is divided into sub-problems. A different sub-problem is identified with each time-frame. These sub-problems are not independent. The dependencies between sub-problems exist because, for any given time-frame, there are constraints on combination of values that can (or cannot) be assumed by state variable inputs. However, explicitly determining all constraints imposed on a time-frame by neighboring time-frames is also difficult. Further, such a determination may be as hard as solving the original test generation problem. This is because prohibitive computational resources may be required to determine all legal and illegal combination of state variable values. Furthermore, the number of sub-problems (time-frames) that will have to be considered for a target fault may not be known. Instead, a partial solution for a sub-problem (corresponding to a time-frame) is determined by ignoring constraints imposed by neighboring time-frames. Such a partial solution may not satisfy an ignored constraint (for example, the partial solution may require a present state that cannot be justified). Adding the unsatisfied constraints augments the initial constraints set for the sub-problem, and thus deriving a new partial solution. Clearly, the time-frame expansion technique employed by sequential test generators is an on-line method.
In other word, on-line methods derive a solution by solving a series of related problems P1 . . . , Pn where:
(1) the constraint set that defines problem Pi(1xe2x89xa6ixe2x89xa6nxe2x88x921) is a subset of the constraint set for problem Pi+1, and
(2) constraints for problem Pi+1 are usually not known while deriving a solution for problem Pi.
If an algorithm is available for finding a solution for P1, one can repeatedly use the same algorithm for deriving solutions for problems P2, . . . , Pn by considering each Pi (1xe2x89xa6ixe2x89xa6n) as independent problems. However, this typically is not an efficient way of finding a solution using on-line methods.
Many problems are often solved by recursively partitioning the problem into sub-problems. Partitioning implies that:
(1) sub-problems can be solved independently, and
(2) solutions to sub-problems can be put together to derive a solution for the original problem.
Sub-problems are independent if the search spaces that will have to be examined for finding sub-problem solutions are independent. However, it should be clear that mandating independence of sub-problems could result in a sub-problem that may be as large as the original problem.
Practitioners in this field know that using recursive partitioning for on-line methods presents additional complications. Even if manageable and independent partitions can be derived for problem Pi, these partitions may not be independent for problem Pi+1. This is because additional constraints included in problem Pi+1 can cause independent sub-problems in Pi to now become dependent.
It is an object of the present invention to provide an improved on-line problem solving method without the above-mentioned problems. It is a specific objective of the present invention to provide an on-line method of solving a test generation problem for sequential circuit wherein partitioned sub-problems can be dependent. It is another specific objective of the present invention to provided an improved method of generating test vectors for testing a sequential circuit.
In order to meet the objects of the present invention there is provided a method of solving a test generation problem for sequential circuits comprising: recursively dividing an original test generation problem into smaller sub-problems, wherein said sub-problems may be dependent while one or more of said dependent sub-problems may have solution-specific independence; finding solutions for said sub-problems: reusing solutions for dependent sub-problems, whenever the dependent sub-problems enjoy solution-specific independence; and identifying a minimal subset of conflicting objectives if a sub-problem that has to be solved to achieve multiple objectives has no solution.
Another aspect of the present invention is a method of generating test vectors for testing a sequential circuit, said method comprising: identifying a test generation problem; selecting a next decision variable; selecting a next value for the decision variable; checking to see if the value selected leads to consistent labeling and returning a conflict set if consistent labeling does not exist; performing the following three sub-steps if said checking finds consistent labeling: partitioning the test generation problem into sub-problems and recursively applying the method of this claim to each of said sub-problems; merging dependent partitions if no solution exists for a current sub-problem and if said dependent partitions exist; exiting if no solution exists for a current subproblem and if dependent partitions do not exist. After performing the above sub-steps, adding variables causing inconsistent labeling if said variables are not part of current partition if said checking leads to inconsistent labeling; repeating for all values of selected variable; repeating for all variables; and returning if solution is found or returning an identified conflict set.
Another aspect of the present invention is a method of solving a problem, said method comprising: recursively dividing the problem into smaller sub-problems, wherein said sub-problems may be dependent while one or more of said dependent sub-problems may have solution-specific independence; finding solutions for said sub-problems; reusing solutions for dependent sub-problems, whenever the dependent sub-problems enjoy solution-specific independence; and identifying a minimal subset of conflicting objectives if a sub-problem that has to be solved to achieve multiple objectives has no solution.
Another aspect of the present invention is a test generation system comprising a computer, said computer having a CPU and memory, said memory comprising instructions capable of implementing components of said system, said components comprising: a test generation problem solver for recursively solving test generation problems wherein solutions for sub-problems are reused: a problem partitioner for receiving test generation problems and partitioning said test generation problems into sub-problems wherein said sub-problems may be dependent and wherein said sub-problems may have solution-specific dependence; a consistent label checker for receiving the test generation problem from the problem solver and determining if there is consistent labeling; a partition merger for merging a subset of sub-problems if no solution exists for said subset of sub-problems and if said subset of sub-problems are dependent; and a conflict set generator for generating a conflict set of objectives that prevents a specific sub-problem from having a solution.
Yet another aspect of the present invention is a computer program product including a compute readable medium with instructions said instruction enabling a computer to solve a test generation problem, said instruction comprising: a test generation problem solver for enabling the computer to recursively solve the test generation problem, wherein solutions for sub-problems are reused; a problem partitioner code for enabling the computer to receive the test generation problem and partition said test generation problems into sub-problems wherein said sub-problems may be dependent and wherein said sub-problems may have solution-specific dependence; a consistent label checker code for enabling the computer to receive the test generation problem from the problem solver and determining if there is consistent labeling; a partition merger code for enabling a computer to merge a subset of sub-problems if no solution exists for said subset of sub-problems and if said subset of sub-problems are dependent; and a conflict set generator code for enabling a computer to generate a conflict set of objectives that prevents a specific sub-problem from having a solution.